package com.leetcode.algorithm.y22.m09.w4;

import java.util.ArrayDeque;
import java.util.Deque;

import com.leetcode.algorithm.common.ListNode;

/**
 * 2130. 链表最大孪生和
 * 
 * https://leetcode.cn/problems/maximum-twin-sum-of-a-linked-list/
 * 
 * @author jie.deng
 *
 */
class Question2130Solution02 {

	public int pairSum(ListNode head) {
		Deque<Integer> deque = new ArrayDeque<>();

		while (head != null) {
			deque.offerLast(head.val);
			head = head.next;
		}

		int max = 0;
		while (!deque.isEmpty()) {
			int right = deque.pollLast().intValue();
			int left = deque.pollFirst().intValue();
			if (right + left > max) {
				max = right + left;
			}
		}
		return max;
	}

}